/**
 * Created by zhangjinrui on 17/6/27.
 */
public class Solution287 {

    public static void main(String args[]){
        Solution287 s = new Solution287();
        System.out.println(s.findDuplicate(new int[]{1,2,3,1,4}));
    }

    public int findDuplicate(int[] nums) {
        int l = 1;
        int r = nums.length - 1;


        while(l < r){
            int mid = l + (r - l) / 2;
            int cnt = 0;
            for(int num : nums){
                cnt += num > mid && num >= l && num <= r ? 1 : 0;
            }
            if(cnt <= (r - l + 1) / 2){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }

}
